package E_2024;

import java.util.Arrays;

/*
题目描述
    某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，
    可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案，输出方案数量。
    约束
    1.一个团只能上一辆车，并且代表团人数(代表团数量小于30,每个代表团人数小于30)小于汽车容量(汽车容量小于100)
    2.需要将车辆坐满
输入描述
    第一行代表团人数，英文逗号隔开，代表团数量小于30,每个代表团人数小于30
    第二行汽车载客量，汽车容量小于100
输出描述
    坐满汽车的方案数量
    如果无解输出0
用例
    输入
    5,4,2,3,2,4.9
    10
    输出
    4
    说明
    解释以下几种方式都可以坐满车，所以，优先接待输出为4
    [2,3,5]
    [2.3.5]
    [2.4.4]
    [2,4,4]
 */
public class E_200_17 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{5, 4, 2, 3, 2, 4, 9}, 10));
    }
    public static int ans(int[] arr,int num){
        Arrays.sort(arr);
        int[][] temp = new int[arr.length + 1][num + 1];
        temp[0][0] = 1;
        for (int i = 1; i <= arr.length; i++) {
            int x = arr[i-1];
            for (int j = 0; j <= num; j++) {
                temp[i][j] = temp[i-1][j];
                if (j >= x)
                    temp[i][j] += temp[i-1][j - x];
            }
        }
        for (int[] ints : temp) {
            System.out.println(Arrays.toString(ints));
        }
        return temp[arr.length][num];
    }
}
